
#include <stdint.h>
#include <string.h>
#include <unistd.h>
#include <fcntl.h>
#include <sys/types.h>
#include <math.h>
#include <assert.h>
#include "blacklist.h"
#include "config.h"
#include "encrypt.h"

/*
The size of the blacklist. The blacklist is implemented as a hashtable, where
the key is a cryptographic hash of a string. Since this is persistent, there is
a risk of songs becoming permanent orphans, if the blacklist is too big.  On
the other hand, if the blacklist is too small, there is a risk that a song
might be chosen again too quickly.  A song remains on the blacklist until a
hash table collision occurs. Once the collision occurs, the song may be picked
again by the choose algorithm.

The probability P that a slot in the blacklist will remain vacant is 

        N(ln(n-1) - lnn)
P(n) = e

where n is the size of the blacklist (_LIST_SIZE), and N is the total number of
songs available. What this amounts to is, n << N. Perhaps 

      N
n = ----
     10

If n ~= N, then very few songs will play more than once.  
*/

#define _LIST_MAX_SIZE 256 
/*
 * If the probability of an orphan ever drops below LOW_P or increases
 * above HIGH_P, the blacklist will be resized to make it equal to P.
 * But in no case will the size of the blacklist exceed LIST_MAX_SIZE.
 */
static uint32_t const LIST_MAX_SIZE = _LIST_MAX_SIZE;
static double const P = 0.001;
static double const LOW_P = 0.0005;
static double const HIGH_P = 0.005;

static uint64_t blacklist [_LIST_MAX_SIZE]; 
static uint32_t list_size = 64;

/*
 * This is the key with which the hashes are computed. 
 * It's completely arbitrary. 
 */
static uint8_t key [16] = {0x01, 0x02, 0x03, 0x04,
	                         0x11, 0x12, 0x13, 0x14, 
													 0x21, 0x22, 0x23, 0x24, 
													 0x31, 0x32, 0x33, 0xFA};

static void resize_blacklist (uint32_t new_size);
static uint64_t hash (char const * const filename);

/*
 * Load the blacklist from a file, if it's there.
 */
void initialize_blacklist (char const * const home)
{
	char blacklist_path [32];
	int fd;
	strncpy (blacklist_path, home, 32);
	strncat (blacklist_path, BLACKLIST, 32);
	fd = open (blacklist_path, O_RDONLY);
	if (fd != -1)
	{
		read (fd, &list_size, sizeof (list_size));
		read (fd, blacklist, sizeof (blacklist [0]) * list_size);
		close (fd);
	}

}

/*
 * Determine whether a song is in the blacklist.
 */
int filter_blacklist (char const * const filename)
{
	uint64_t the_hash;
	the_hash = hash (filename);
	if (the_hash == blacklist [the_hash % list_size])
	{
		return 0;
	}
	return 1;
}

/*
 * Put a song into the blacklist.
 */
void insert_blacklist (char const * const filename)
{
	uint64_t the_hash;
	the_hash = hash (filename);
	blacklist [the_hash % list_size] = the_hash;
}

/*
 * Resize the blacklist, if necessary.
 */
void update_blacklist (uint32_t const count)
{
	double p;
	double exponent;
	double NrootP;
	uint32_t new_size;
	p = exp (count * (log (list_size - 1) - log (list_size)));
	if ((p <= LOW_P || p >= HIGH_P))
	{
		exponent = 1.0 / (double) count;
		NrootP = pow (P, exponent);
		new_size = (uint32_t) floor (-1 / (NrootP - 1));
		if (new_size > LIST_MAX_SIZE)
		{
			new_size = LIST_MAX_SIZE;
		}
		if (new_size < 1)
		{
			new_size = 1;
		}
		resize_blacklist (new_size);
	}
}

/*
 * Resize the blacklist. If elements that didn't collide 
 * at the previous size now collide, one of them will be 
 * freed. 
 */
static void resize_blacklist (uint32_t new_size)
{
	uint64_t tmp_list [LIST_MAX_SIZE];
	uint64_t tmp;
	uint32_t i;
	assert (new_size <= LIST_MAX_SIZE);
	for (i = 0; i < list_size; i ++)
	{
		tmp_list [i] = blacklist [i];
	}
	for (i = 0; i < list_size; i ++)
	{
		tmp = tmp_list [i];
		if (tmp != 0)
		{
			blacklist [tmp % new_size] = tmp;
		}
	}
	list_size = new_size;
}

/*
 * Store the blacklist to a file.
 */
void finalize_blacklist (char const * const home)
{
	char blacklist_path [32];
	int fd;
	strncpy (blacklist_path, home, 32);
	strncat (blacklist_path, BLACKLIST, 32);
	fd = open (blacklist_path, O_WRONLY | O_TRUNC | O_CREAT, 0644);
	write (fd, &list_size, sizeof (list_size));
	write (fd, blacklist, sizeof (blacklist [0]) * list_size);
	close (fd);
}

/*
 * Compute a cryptographic hash of the filename. This is equivalent 
 * to using key to encrypt filename in CBC mode, and discarding all 
 * but the last block of ciphertext. 
 */
static uint64_t hash (char const * const filename)
{
	int bytes_hashed;
	int bytes_to_hash;
	uint64_t the_hash = 0;
	uint64_t block = 0;
	bytes_to_hash = strlen (filename);
	bytes_hashed = 0;
	while (bytes_hashed < bytes_to_hash)
	{
		strncpy ((char *) &block, filename + bytes_hashed, BLOCK_SIZE);
		bytes_hashed = bytes_hashed + BLOCK_SIZE; 
		block = block ^ the_hash;
		block_encrypt (key, (uint8_t *) &block, (uint8_t *) &the_hash);
	}
	return the_hash;
}

